/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/4sum
   @Language: C++
   @Datetime: 19-05-30 11:28
   */

// Method 1, Time O(n*n), Space O(n*n), Time 108ms
class Solution {
	struct hashvec{
		size_t operator()(const vector<int> &v)const{
			string str;
			for(int i=0; i<v.size(); ++i)
				str.append(to_string(v[i]));
			return hash<string>()(str);
		}
	};
public:
	vector<vector<int> > fourSum(vector<int>& nums, int target) {
		sort(nums.begin(),nums.end());
		unordered_multimap<int,pair<int,int> > sums;
		for(int i=0; i<nums.size(); ++i){
			if(i>0 && nums[i-1]==nums[i]) continue;
			for(int j=i+1; j<nums.size(); ++j){
				if(j>i+1 && nums[j-1]==nums[j]) continue;
				sums.insert(make_pair(nums[i]+nums[j],make_pair(i,j)));
			}
		}
		vector<vector<int> > res;
		unordered_set<vector<int>,hashvec> visit;
		for(int i=0; i<nums.size(); ++i){
			for(int j=i+1; j<nums.size(); ++j){
				auto r=sums.equal_range(target-nums[i]-nums[j]);
				for(; r.first!=r.second; r.first++){
					auto f=r.first;
					if(f->second.first==i || f->second.first==j ||
							f->second.second==i || f->second.second==j) continue;
					vector<int> cans={nums[i], nums[j], nums[f->second.first], nums[f->second.second]};
					sort(cans.begin(),cans.end());
					if(visit.count(cans)) continue;
					visit.insert(cans);
					res.push_back(cans);
				}
			}
		}
		return res;
	}
};

// Method 2, Time O(n*n*n), Space O(1), Time 84ms
class Solution {
public:
	vector<vector<int> > fourSum(vector<int> &A, int tar) {
		// write your code here
		vector<vector<int> > vs;
		sort(A.begin(),A.end());					// ascending order
		for(int i=0; i<A.size(); ++i){
			if (i>0 && A[i-1]==A[i]) continue;		// duplication
			for(int j=i+1; j<A.size(); ++j){
				if (j>i+1 && A[j-1]==A[j]) continue;// duplication
				for(int k=j+1, l=A.size()-1; k<l;){
					if (k>j+1 && A[k-1]==A[k]){
						++k;						// duplication
						continue;
					}
					if (l<A.size()-1 && A[l]==A[l+1]){
						--l;						// duplication
						continue;
					}
					int sum = A[i]+A[j]+A[k]+A[l];
					if (sum > tar) --l;
					else if (sum < tar) ++k;
					else {
						vector<int> v(4,A[i]);
						v[1]=A[j], v[2]=A[k++], v[3]=A[l--];
						vs.push_back(v);
					}
				}
			}
		}
		return vs;
	}
};
